HDU6346 整数规划

给定$n×n$个整数$a_{ij}(1<=i,j<=n)$，要找$2n$个整数$x_1,x_2,x_3…x_n,y_1,y_2,y_3…y_n$,在满足$x_i+y_i<=a_{ij}(1<=i,j<=n)$的约束下最大化目标函数
$$\sum_{i=1}^{n}{x_i}+\sum_{i=1}^{n}{y_i} \ \ (n<=200)$$

---

题解

可以构造一个完全二分图$K_{n,m}$，左边第$i$个点和右边第$j$点之间连一条权值为 $a_{ij}$ 的边，现在是要计算最大顶标和，而在这道题中正好就是最小权匹配，正确使用KM即可